package algorithms;

/**
 * 快排的基本思想：把数组划分成左右两个区域，左边的区域小于等于 指定值，右边的区域大于 指定值。
 * <p>
 * 最难的部分就是找到这个指定值对应的索引。区域的划分方法：
 * i指向左边区域，i++就是扩容左边区域； j指向右边区域，j++就是扩容右边区域；
 * 用j遍历元素，发现比指定值小的，就放到i指向的左边区域；发现比指定值大的，就放到j指向的右边区域。
 * <p>
 * i+1就是j指向的区域的最左边（含最左边元素）。
 */
public class 快速排序 {

    public static void main(String[] args) {
        int[] a = new int[]{4, 8, 1, 0, 2, 5, 5, 9, 7, 6, 3, 3};
        quickSort(a, 0, a.length - 1);
        printArr(a);
    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivotIndex = partitionThenReturnPivotIndex(arr, start, end);
        quickSort(arr, start, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, end);
    }

    private static int partitionThenReturnPivotIndex(int[] a, int start, int end) {
        int i = start - 1;
        int j = start;
        int pivot = a[end];
        for (; j <= end - 1; j++) {
            if (a[j] <= pivot) {
                //这个加1的操作，就是扩展区域的过程
                i = i + 1;
                exchange(a, i, j);
            }
        }
        exchange(a, i + 1, end);
        return i + 1;
    }

    private static void exchange(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}
